import java.util.*;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-11-04
 * Time: 8:32
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class BinarySearchTree {
    public static TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode cur=root;
        if(cur==null){
            return new TreeNode(val);
        }
        //迭代版
        /*
        TreeNode cur = root;
        while(cur!=null){
            if(val<cur.val){//走左树
                 //先判定左树是否为空，为空直接插入
                if(cur.left==null){
                    cur.left=new TreeNode(val);
                    break;
                }else{
                    cur=cur.left;
                }
            }else{//走右子树
                   //先判定右子树是否为空
                if(cur.right==null){
                    cur.right=new TreeNode(val);
                    break;
                }else{
                    cur=cur.right;
                }
            }
        }
        return root;

         */
        //递归版
        if(cur.val<val){
            cur.right=insertIntoBST(cur.right,val);//返回右子树根节点
        }else{
            cur.left=insertIntoBST(cur.left,val);//返回左子树根节点
        }
        return root;
    }
    }
}
